/*
 * @Author: szx
 * @Date: 2022-03-26 13:30:24
 * @LastEditTime: 2022-03-26 14:08:50
 * @Description:
 * @FilePath: \leetcode\剑指offer\51\51.js
 */
/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function (nums) {
    const n = nums.length;
    let res = 0;
    for (let i = 0; i < n - 1; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[i] > nums[j]) res++;
        }
    }
    return res;
};

var reversePairs = function (nums) {
    let res = 0;
    const n = nums.length;
    const arr = new Array(n).fill(0);
    const mergeSort = (nums, left, right) => {
        if (left >= right) return;
        const mid = Math.floor((left + right) / 2);
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        let i = left;
        let j = mid + 1;
        let k = 0;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) arr[k++] = nums[i++];
            else {
                arr[k++] = nums[j++];
                res += mid - i + 1;
            }
        }
        while (i <= mid) arr[k++] = nums[i++];
        while (j <= right) arr[k++] = nums[j++];
        for (let i = left; i <= right; i++) nums[i] = arr[i - left];
    };
    mergeSort(nums, 0, n - 1);
    return res;
};
console.log(reversePairs[(7, 5, 6, 4)]);
